The proliferation of smart phones and other mobile devices has placed more processing power in the hands of consumers than ever before. These mobile devices are capable of executing a variety of applications, including applications that assist with navigation and route-finding. Traditional global positioning system (GPS) navigation devices are used to assist automobile owners with driving operations from a source to a destination, and navigation software is generally developed with the use-case of driving directions in mind. These devices may provide map data in the form of a road graph, with valid driving paths represented by line segments which intersect at various points, and which have a directionality element indicating valid directions of travel along the line segments. Such a design is efficient for use in situations where the user is travelling via a vehicle, as the vehicle is limited to particular pathways of travel.
However, as mobile devices increasingly contain route finding software, various solutions that provide for walking and indoor navigation have also been developed. The road graph as described above is not suitable for a walking or indoor environment because it may be overly complicated for a mobile device to process, and because users generally travel within open space, rather than along set pathways. When finding the path between two points on a map in a road graph model, if an end point is not located on the road, the end point may be approximated by a point on a road using a metric such as the shortest distance to the point. For this reason, such representations may not be optimal for areas with open space or other navigable space that cannot be efficiently represented by line segments. For example, an indoor map using a road graph representation might represent hallways and corridors as line segments. Such a representation may incorrectly identify a user as located within a hallway when in fact they are present in a room connected to that hallway. Thus, navigation map data provided by a road graph may be overly complicated and inefficient for the purposes of providing a representation of an indoor navigation environment.